/*
题目链接：https://leetcode.cn/problems/minimum-height-trees/
提交题目：310.最小高度树
提交时间：2024/10/10
*/

class Solution {
public:
    //用于计算从节点u出发到所有其他节点的最短距离，并记录每个节点的父节点 
    void dfs(int u,vector<int>&dist,vector<int>&p,vector<vector<int>>&a){
        for(auto v:a[u]){      //遍历节点u的所有邻接节点v  
            if(dist[v]<0){   //如果节点v尚未被访问（即dist[v]仍为初始值-1）则进入 
                dist[v]=dist[u]+1;
                p[v]=u;       //记录节点v的父节点为u 
                dfs(v,dist,p,a);
            }
        }
    }

    int findlong(int u,vector<int>&p,vector<vector<int>>&a){
        int n=a.size();  //获取结点总数
        vector<int>dist(n,-1);   //初始化距离数组，所有节点的距离初始化为-1 
        dist[u]=0;    //节点u到自身的距离为0
        dfs(u,dist,p,a);   //从节点u开始深度优先搜索
        int maxdist=0;
        int node=0;
        for(int i=0;i<n;i++){   //找到距离结点u的最远节点
            if(dist[i]>maxdist){
                maxdist=dist[i];  //更新距离节点u的最远距离
                node=i;   //更新距离节点u最远距离的结点标号
            }
        }
        return node;  
    }

    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if(n == 1) return {0};  // 当节点只有1个时，则答案为节点0本身

        //构建邻接链表，将所有边按关系存入
        vector<vector<int>>a(n);  //初始化，有n个结点
        for(auto edge:edges){
            a[edge[0]].push_back(edge[1]);
            a[edge[1]].push_back(edge[0]);
        }

        vector<int>p(n,-1);   //初始化父节点数组

        //从节点0出发，找到离节点0最远的结点x
        int x=findlong(0,p,a);

        //从结点x出发，找到离结点x最远的节点y
        int y=findlong(x,p,a);

        //找到节点x到节点y路径中的所有节点
        vector<int>node;
        p[x]=-1;   //将节点x的父节点设为-1，避免重复加入路径 
        while(y!=-1){
            node.push_back(y);
            y=p[y];
        }
        int m=node.size();  //节点个数
        if(m%2==0){   //节点个数为偶数，则路径是m-1为奇数，符合条件的根节点有两个
            return {node[m/2-1],node[m/2]};  
        }
        else{         //节点个数为奇数，则路径是m-1为偶数，符合条件的根节点只有一个
            return {node[m/2]};
        }
    }
};
